#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;
class Solution {
private:
    bool findOrderCore(unordered_map<int, vector<int>>& graph, unordered_set<int>& hasVisited,
        unordered_set<int>& needVisited,
        vector<int>& path, int current) {
        if (needVisited.find(current) != needVisited.end())
            return false;
        if (hasVisited.find(current) != hasVisited.end())
            return true;
        auto item = graph.find(current);
        if (item != graph.end()) {
            for (auto& pre : item->second) {
                needVisited.insert(current);
                if (!findOrderCore(graph, hasVisited, needVisited, path, pre))
                    return false;
                needVisited.erase(current);
            }
        }
        hasVisited.insert(current);
        path.push_back(current);
        return true;
    }
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> graph;
        for (int i = 0; i < prerequisites.size(); ++i) {
            graph[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        vector<int> path;
        unordered_set<int> hasVisited;
        unordered_set<int> needVisited;
        for (int i = 0; i < numCourses; ++i)
            if (!findOrderCore(graph, hasVisited, needVisited, path, i)) {
                path.clear();
                break;
            }
        return path;
    }
};